package NiuKe.JianZhiOffer;
import java.util.*;

/**
 * 描述
 * 输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 * 示例1
 * 输入：
 * {10,5,12,4,7},22
 *
 * 返回值：
 * [[10,5,7],[10,12]]
 *
 * 示例2
 * 输入：
 * {10,5,12,4,7},15
 *
 * 返回值：
 * []
 */
public class JZ24 {

    ArrayList<ArrayList<Integer>> arrayList = new  ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null) return arrayList;
        Find(root,target,new ArrayList<Integer>());
        return arrayList;

    }

    public void Find(TreeNode root,int target,ArrayList list){
        target = target - root.val;
        list.add(root.val);

        if(root.left == null && root.right == null ){
            if( target == 0 ){
                arrayList.add(list);
            }
        }

        if(root.left != null){
            ArrayList<Integer> listClone = (ArrayList)list.clone();
            Find(root.left,target,listClone);
        }

        if(root.right != null){
            Find(root.right,target,list);
        }
    }

}
